The framework of formulating the feedback structure as feedback graphs in bandits has a long history (Mannor and Shamir, 2011; Alon et al., 2015, 2017; Lykouris et al.,

While contextual bandit has a mature theory, effectively leveraging different feedback patterns to enhance the pace of learning remains unclear.

We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious adversaries is O( αT), where T is the time horizon andα is the independence number of the feedback graph.

The framework of feedback graphs is a generalizationof sequential decisionmaking with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical Erdős-Rényi model. Specifically, in each round every edge in the graph is either realized or not with a distinct probability for each edge.

Here, θ() is the clique coveringnumberofthegraph. Online learning models a repeated interaction between a learner and an environment.

This study considers online learning with general directed feedback graphs.